МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ Національний університет “Львівська політехніка” Кафедра САП
Звіт до лабораторної роботи № 1 МАШИНА ПОСТА з курсу «Алгоритми і структури даних» для студентів спеціальності "Комп’ютерні системи проектування"  Львів 2013 МЕТА РОБОТИ Мета роботи – вивчення формального визначення поняття алгоритму, пов’язаного із введеною Емілем Постом спеціальної математичної конструкції (машина Поста) і постулюванням тези про еквівалентність такого формалізму і поняття «алгоритм». ТЕОРЕТИЧНІ ВІДОМОСТІ Однією із фундаментальних статей, результати якої лежать в основі сучасної теорії алгоритмів, є стаття польсько-американського математика і логіка Еміля Леона Поста (1897-1954), «Finite combinatory processes - Formulation 1» , опубліковану у 1936 році. У ній він запропонував абстрактну обчислювальну конструкцію, яка дозволила вперше уточнити поняття алгоритму і яку згодом назвали машиною Поста. При розробці обчислювальної конструкції Пост керувався принципом створення максимально простої абстракції: мінімум операцій під час обробки інформації, вхідна інформація повинна бути закодованою з використанням мінімального набору символів. Не дивлячись на примітивність машини Поста, будь-який існуючий алгоритм може бути записаний у вигляді програми для машини Поста. У теорії алгоритмів існує так звана «теза Поста»: «Будь-який алгоритм можна представити у вигляді машини Поста». Ця теза одночасно є і формальним визначенням алгоритму. Алгоритм (за Постом) - програма для машини Поста, що приводить до вирішення поставленої задачі. Теза Поста є гіпотезою. Її неможливо строго довести (так само, як і теза Тюрінга), тому що у ній фігурують, з одного боку, інтуїтивне поняття «будь-який алгоритм», а з іншого боку - точне поняття «машина Поста». Для того, щоб спростувати гіпотезу Поста, необхідно придумати алгоритм, який неможливо записати у вигляді програми для машини Поста. На сьогоднішній день такого алгоритму не існує. Машина Поста — це абстрактна (тобто така, що не існує в арсеналі техніки), але дуже проста обчислювальна машина. Машина Поста, не дивлячись на зовнішню простоту, може здійснювати різні обчислення, для чого потрібно задати початковий стан каретки і програму, яка виконає ці обчислення. Машиною ця математична конструкція названа тому, що при її побудові використовуються деякі поняття реальних машин (елемент пам’яті, команда тощо). Машину Поста можна розглядати як спрощену модель комп’ютера. Насправді, як комп’ютер, так і машина Поста мають: неподільні носії інформації (комірки — біти), які можуть бути заповненими або незаповненими; обмежений набір елементарних дій — команд, кожна з яких виконується за один такт (крок). Обидві машини працюють на основі програми. Проте у машині Поста інформація розташовується лінійно і читається підряд, а в комп’ютері можна читати інформацію за адресою; набір команд комп’ютера значно ширший і виразніший за команди машини Поста. Склад машини Поста Машина Поста складається із стрічки та каретки (яка також називається головкою зчитування/запису). Стрічка є безмежною і розділена на комірки однакового розміру (рис.1.1).
Рис. 1.1. Каретка завжди вказує на одну із комірок Комірка стрічки може бути порожньою, або у ній може перебувати мітка. Інформація про те, які комірки порожні, а які містять мітки, утворює стан стрічки. Іншими словами, стан стрічки — це розподіл міток по комірках. Стан стрічки змінюється у процесі роботи машини. Зауважимо, що наявність міток у комірці можна інтерпретувати як «1», а відсутність як «0». Таке двійкове представлення інформації подібне до уявлення, яке використовується практично у всіх сучасних комп’ютерах. Каретка може пересуватися вздовж стрічки вліво і вправо. Коли вона нерухома — вона перебуває навпроти однієї комірки стрічки. У такому випадку говорять, що каретка оглядає одну комірку. За одиницю часу каретка може зробити одну із трьох дій: стерти мітку, поставити мітку, зробити рух до сусідньої комірки. С...